{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 定义新的数据类型\n",
    "- 使用`data`关键字可以定义新的数据类型:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "data BookInfo = Book Int String [String]\n",
    "                deriving (Show)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mb = Just 1\n",
    "mb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- BookInfo 就是新类型的名字，我们称为类型构造器。类型构造器用于指代(refer)类型。\n",
    "- Book则是值构造器（也称数据构造器）的名字。\n",
    "- 类型构造器和值构造器的首字母都需要大写\n",
    "- 在Book之后的Int,String和[String]是类型的组成部分。组成部分的作用，和面向对象语言中类的域作用一致：它是一个存储值的槽。（通常也将组成部分称为域。）\n",
    "- 类型包含的成分结构相同但是不可用混用，比如我们定义一个`MagzineInfo`类型的成分和BookInfo一模一样，但是Haskell会将它们作为不同的类型来区别对待，因为他们的类型构造器和值构造器并不相同:\n",
    "- 在ghci中我们可以使用:info查看更多关于给定表达式的信息，使用:type命令，可以查看值构造器的类型签名，了解他们是如果创造出类型的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 类型构造器和值构造器的命名"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 在Haskell里，类型的名字(类型构造器)和值构造器的名字是相互独立的。\n",
    "- 类型构造器只能出现在类型的定义，或者类型签名当中。而值构造器只能出现在具体的代码中。\n",
    "- 所以给类型构造器和值构造器赋予相同名字是没问题的，但是应当注意两者是不同的概念。而大部分oop语言是混杂到一起的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 类型别名"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 可以使用类型别名，来为一个已存在的类型设置一个更具描述性的名字\n",
    "- 比如:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "type CustomerID =  Int\n",
    "type ReviewBody = String\n",
    "\n",
    "data BookReview = BookReview BookInfo CustomerID ReviewBody"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 与oop里面使用变量名来赋予某个字段具体的含义相比，这样无疑是更加优越的，比如人名和书名都是String,可是确实应当有能力使两者不混为一谈\n",
    "- 还可以为复杂的类型设置一个简短的名字:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "type BookRecord = (BookInfo,BookReview)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 类型别名只是为已有类型提供一个新名字而已，创建值的工作仍然由原来的类型的值构造器进行。(可以类比C/C++中的typedef)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 代数数据类型\n",
    "- Bool类型是代数数据类型(algebraic data type)的最简单，最常见的例子，一个代数数据类型可以有多于一个值构造器:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "data Bool = False | True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面代码定义的 Bool 类型拥有两个值构造器，一个是 True ，另一个是 False 。每个值构造器使用 | 符号分割，读作“或者” —— 以 Bool 类型为例子，我们可以说， Bool 类型由 True 值或者 False 值构成。\n",
    "\n",
    "当一个类型拥有一个以上的值构造器时，这些值构造器通常被称为“备选”（alternatives）或“分支”（case）。同一类型的所有备选，创建出的的值的类型都是相同的。\n",
    "\n",
    "代数数据类型的各个值构造器都可以接受任意个数的参数。[译注：不同备选之间接受的参数个数不必相同，参数的类型也可以不一样。]以下是一个账单数据的例子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "type CardHolder = String\n",
    "type CardNumber = String\n",
    "type Address = [String]\n",
    "data BillingInfo = CreditCard CardNumber CardHolder Address\n",
    "                 | CashOnDelivery\n",
    "                 | Invoice CustomerID\n",
    "                   deriving (Show)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个程序提供了三种付款的方式。如果使用信用卡付款，就要使用 CreditCard 作为值构造器，并输入信用卡卡号、信用卡持有人和地址作为参数。如果即时支付现金，就不用接受任何参数。最后，可以通过货到付款的方式来收款，在这种情况下，只需要填写客户的 ID 就可以了。\n",
    "\n",
    "当使用值构造器来创建 BillingInfo 类型的值时，必须提供这个值构造器所需的参数：\n",
    "\n",
    "```\n",
    "Prelude> :load BookStore.hs\n",
    "[1 of 1] Compiling Main             ( BookStore.hs, interpreted )\n",
    "Ok, modules loaded: Main.\n",
    "\n",
    "*Main> :type CreditCard\n",
    "CreditCard :: CardNumber -> CardHolder -> Address -> BillingInfo\n",
    "\n",
    "*Main> CreditCard \"2901650221064486\" \"Thomas Gradgrind\" [\"Dickens\", \"England\"]\n",
    "CreditCard \"2901650221064486\" \"Thomas Gradgrind\" [\"Dickens\",\"England\"]\n",
    "\n",
    "*Main> :type it\n",
    "it :: BillingInfo\n",
    "```\n",
    "如果输入参数的类型不对或者数量不对，那么引发一个错误：\n",
    "\n",
    "```\n",
    "*Main> Invoice\n",
    "\n",
    "<interactive>:7:1:\n",
    "    No instance for (Show (CustomerID -> BillingInfo))\n",
    "        arising from a use of `print'\n",
    "    Possible fix:\n",
    "        add an instance declaration for (Show (CustomerID -> BillingInfo))\n",
    "    In a stmt of an interactive GHCi command: print it\n",
    "\n",
    "```\n",
    "ghci 抱怨我们没有给 Invoice 值构造器足够的参数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 元组和代数数据类型的使用场景\n",
    "元组和自定义代数数据类型有一些相似的地方。比如说，可以使用一个 (Int, String, [String]) 类型的元组来代替 BookInfo 类型：\n",
    "```\n",
    "*Main> Book 2 \"The Wealth of Networks\" [\"Yochai Benkler\"]\n",
    "Book 2 \"The Wealth of Networks\" [\"Yochai Benkler\"]\n",
    "\n",
    "*Main> (2, \"The Wealth of Networks\", [\"Yochai Benkler\"])\n",
    "(2,\"The Wealth of Networks\",[\"Yochai Benkler\"])\n",
    "```\n",
    "\n",
    "代数数据类型使得我们可以在结构相同但类型不同的数据之间进行区分。然而对于元组来说，要元素的结构和类型都一致，那么元组的类型就是相同的,而对于两个不同的代数数据类型来说，即时值构造器成分的结构和类型都相同，它们也是不同的类型。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 其他语言里类似代数数据类型的东西\n",
    "- 代数数据类型为描述数据类型提供了一种单一且强大的方式。很多其他语言，要达到相当于代数数据类型的表达能力，需要同时使用多种特性。\n",
    "- 以下用C/C++举例"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 结构\n",
    "- 当只有一个值构造器时，代数数据类型和元组很相似：它将一系列相关的值打包成一个复合值。这种做法相当于 C 和 C++ 里的 struct ，而代数数据类型的成分则相当于 struct 里的域。\n",
    "\n",
    "- 以下是一个 C 结构，它等同于我们前面定义的 BookInfo 类型：\n",
    "```\n",
    "struct book_info {\n",
    "    int id;\n",
    "    char *name;\n",
    "    char **authors;\n",
    "};\n",
    "```\n",
    "- 目前来说， C 结构和 Haskell 的代数数据类型最大的差别是，代数数据类型的成分是匿名且按位置排序的：\n",
    "\n",
    "```\n",
    "data BookInfo = Book Int String [String]\n",
    "                deriving (Show)\n",
    "```\n",
    "- 按位置排序指的是，对成分的访问是通过位置来实行的，而不是像 C 那样，通过名字：比如 book_info->id 。\n",
    "\n",
    "- 稍后的“模式匹配”小节会介绍如何访代数数据类型里的成分。在“记录”一节会介绍定义数据的新语法，通过这种语法，可以像 C 结构那样，使用名字来访问相应的成分。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 枚举\n",
    "C 和 C++ 里的 enum 通常用于表示一系列符号值排列。代数数据类型里面也有相似的东西，一般称之为枚举类型。\n",
    "\n",
    "以下是一个 enum 例子：\n",
    "```\n",
    "enum roygbiv {\n",
    "    red,\n",
    "    orange,\n",
    "    yellow,\n",
    "    green,\n",
    "    blue,\n",
    "    indigo,\n",
    "    violet,\n",
    "};\n",
    "```\n",
    "以下是等价的 Haskell 代码：\n",
    "\n",
    "```\n",
    "data Roygbiv = Red\n",
    "             | Orange\n",
    "             | Yellow\n",
    "             | Green\n",
    "             | Blue\n",
    "             | Indigo\n",
    "             | Violet\n",
    "```\n",
    "enum 的问题是，它使用整数值去代表元素：在一些接受 enum 的场景里，可以将整数传进去，C 编译器会自动进行类型转换。同样，在使用整数的场景里，也可以将一个 enum 元素传进去。这种用法可能会造成一些令人不爽的 bug 。\n",
    "\n",
    "另一方面，在 Haskell 里就没有这样的问题。比如说，不可能使用 Roygbiv 里的某个值来代替 Int 值[译注：因为枚举类型的每个元素都由一个唯一的值构造器生成，而不是使用整数表示。]："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 联合\n",
    "如果一个代数数据类型有多个备选，那么可以将它看作是 C 或 C++ 里的 union 。\n",
    "\n",
    "以上两者的一个主要区别是， union 并不告诉用户，当前使用的是哪一个备选， union 的使用者必须自己记录这方面的信息（通常使用一个额外的域来保存），这意味着，如果搞错了备选的信息，那么对 union 的使用就会出错。\n",
    "\n",
    "以下是一个 union 例子：\n",
    "```\n",
    "enum shape_type {\n",
    "    shape_circle,\n",
    "    shape_poly,\n",
    "};\n",
    "\n",
    "struct circle {\n",
    "    struct vector centre;\n",
    "    float radius;\n",
    "};\n",
    "\n",
    "struct poly {\n",
    "    size_t num_vertices;\n",
    "    struct vector *vertices;\n",
    "};\n",
    "\n",
    "struct shape\n",
    "{\n",
    "    enum shape_type type;\n",
    "    union {\n",
    "    struct circle circle;\n",
    "    struct poly poly;\n",
    "    } shape;\n",
    "};\n",
    "```\n",
    "在上面的代码里， shape 域的值可以是一个 circle 结构，也可以是一个 poly 结构。 shape_type 用于记录目前 shape 正在使用的结构类型。\n",
    "\n",
    "另一方面，Haskell 版本不仅简单，而且更为安全：\n",
    "\n",
    "```\n",
    "type Vector = (Double, Double)\n",
    "\n",
    "data Shape = Circle Vector Double\n",
    "           | Poly [Vector]\n",
    "```\n",
    "\n",
    "注意，我们不必像 C 语言那样，使用 shape_type 域来手动记录 Shape 类型的值是由 Circle 构造器生成的，还是由 Poly 构造器生成， Haskell 自己有办法弄清楚一点，它不会弄混两种不同的值。其中的原因，下一节《模式匹配》就会讲到。\n",
    "\n",
    "[译注：原文这里将 Poly 写成了 Square 。]\n",
    "- 个人认为，要从发展的角度来看，C/C++本就是从底层一路抽象上来，C里面的struct是要直接关联内存分配大小的，这意味着C注定无法在语义的表达上与Haskell角力，但是Haskell最终也是要编译到二进制代码在冯诺依曼的体系上执行的，只是编译器帮我们屏蔽了底层的内存分配要考虑的问题。所以，我当然想用Haskell去描述我的逻辑，但也不意味着无脑鼓吹，捧一贬一。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 模式匹配\n",
    "- 上面介绍了定义代数数据类型的方法。接下来说明怎样去处理这些类型的值\n",
    "- 对于某个类型的值来说，应该可以做到以下两点:\n",
    "    1. 如果这个类型有一个以上的值构造器，那么应该可以知道，这个值是由哪个构造器创建的。\n",
    "    2. 如果一个值构造器包含不同的成分，那么应该有办法提取这些成分。\n",
    "- 对于以上两个问题，Haskell有一个简单且有效的解决方式，那就是类型匹配。\n",
    "- 模式匹配允许我们查看值的内部，并将值所包含的数据绑定到变量上。以下是一个对 Bool 类型值进行模式匹配的例子，它的作用和 not 函数一样：\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "myNot True = False\n",
    "myNot False = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 对于名字相同的函数,Haskell允许定义函数在不同输入参数模式下的不同行为,当调用函数式，Haskell会去匹配同名不同模式的函数，如果匹配成功则调用执行。\n",
    "- 对于每行等式，模式定义放在函数名之后， = 符号之前。\n",
    "- 一个更复杂的例子，以下函数是计算出列表所有元素之和:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Use foldr</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">sumList (x : xs) = x + sumList xs\n",
       "sumList [] = 0</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">sumList xs = foldr (+) 0 xs</div></div>"
      ],
      "text/plain": [
       "Line 1: Use foldr\n",
       "Found:\n",
       "sumList (x : xs) = x + sumList xs\n",
       "sumList [] = 0\n",
       "Why not:\n",
       "sumList xs = foldr (+) 0 xs"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sumList (x:xs) = x+sumList xs\n",
    "sumList [] = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 需要说明的是，在Haskell里，列表[1,2],其实只是(1:(2:[]))的一种简单的表示方式，其中`:`用于构造列表:\n",
    "```\n",
    "Prelude> []\n",
    "[]\n",
    "\n",
    "Prelude> 1:[]\n",
    "[1]\n",
    "\n",
    "Prelude> 1:2:[]\n",
    "[1,2]\n",
    "```\n",
    "- 因此，当需要对一个列表进行匹配时，也可以使用`:`操作符，只不过这次不是用来构造列表，而是用来分解列表。\n",
    "- 继续考虑sumList,如果用sumLis去求值[1,2]，首先[1,2]会匹配到(x:xs)，于是x被绑定1,xs被绑定[2],此时表达式就变成了1+(sumList([2]))，后续的情况就类似。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sumList [1,2]\n",
    "sum [1,2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 组成和解构\n",
    "- 让我们梳理一下构造一个值和对值进行模式匹配之间的关系\n",
    "    - 描述一个构造值的过程: 表达式 `Book 9 \"Close Calls\" [\"John Long\"]` 应用 `Book Int String [String]` 构造器到值 9 、 \"Close Calls\" 和 [\"John Long\"] 上面，从而产生一个新的 BookInfo 类型的值。\n",
    "    - 而当我们对Book构造器进行模式匹配时，我们在逆转(reverse)它的构造过程: 首先，检查这个值是否由 Book 构造器生成 —— 如果是的话，那么就对这个值进行探查（inspect），并取出创建这个值时，提供给构造器的各个值。\n",
    "    \n",
    "- 考虑一下表达式 Book 9 \"Close Calls\" [\"John Long\"] 对模式 (Book id name authors) 的匹配是如何进行的：\n",
    "\n",
    "    - 因为值的构造器和模式里的构造器相同，因此匹配成功。\n",
    "    - 变量 id 被绑定为 9 。\n",
    "    - 变量 name 被绑定为 Close Calls 。\n",
    "    - 变量 authors 被绑定为 [\"John Long\"] 。\n",
    "- 因为模式匹配的过程像是逆转一个值的构造(construction)过程，因此它有时候也被称为结构(deconstruction)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 更进一步\n",
    "- 对元组进行模式匹配的语法，和构造元组的语法很相似。\n",
    "- 以下是一个可以返回三元组中最后一个元素的函数:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "third (a,b,c) = c\n",
    "third (1,2,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 模式匹配的“深度”并没有限制，以下模式会同时对元组和元组里的列表进行匹配,匹配失败则会报错"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "complicated (True, a, x:xs,5) = (a,xs)\n",
    "-- complicated (True, 1, [1,2,3], 5)\n",
    "-- complicated (False, 1, [1,2,3], 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 对代数数据类型的匹配，可以通过这个类型的值构造器来进行。用前面定义的BookInfo类型为例，对它可以使用它的Book构造器来进行:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\"Probability Theory\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[\"E.T.H Jaynes\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\"Probability Theory\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bookID      (Book id title authors) = id\n",
    "bookTitle   (Book id title authors) = title\n",
    "bookAuthors (Book id title authors) = authors\n",
    "\n",
    "\n",
    "book = Book 3 \"Probability Theory\" [\"E.T.H Jaynes\"]\n",
    "bookID book\n",
    "bookTitle book\n",
    "bookAuthors book\n",
    "\n",
    "-- 字面值的对比规则对于列表和值构造器的匹配也适用，比如这里只匹配id=3的\n",
    "bookIdEq3    (Book 3 title authors) = title\n",
    "bookIdEq3 book    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 模式匹配中的变量名命名\n",
    "当你阅读那些进行模式匹配的函数时，经常会发现像是 (x:xs) 或是 (d:ds) 这种类型的名字。这是一个流行的命名规则，其中的 s 表示“元素的复数”。以 (x:xs) 来说，它用 x 来表示列表的第一个元素，剩余的列表元素则用 xs 表示。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 通配符模式匹配\n",
    "- 如果在匹配模式中我们不在乎某个值的类型，那么可以用下划线字符 “_” 作为符号来进行标识，它也叫做通配符。它的用法如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "nicerID      (Book id _     _      ) = id\n",
    "nicerTitle   (Book _  title _      ) = title\n",
    "nicerAuthors (Book _  _     authors) = authors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 显然我们使用变量也是可以达到同样的匹配效果，但是使用通配符去匹配我们不会使用的值会使得可读性更高，所以当我们匹配列表中定义了变量但是函数体中却没有使用，Haskell编译器会给出一个警告，这往往意味着潜在的bug"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 穷举匹配模式和通配符\n",
    "- 在给一个类型写一组匹配模式时，很重要的一点就是一定要涵盖构造器的所有可能情况。例如，如果我们需要探查一个列表，就应该写一个匹配非空构造器 (:) 的方程和一个匹配空构造器 [] 的方程。\n",
    "\n",
    "- 假如我们没有涵盖所有情况会发生什么呢。下面，我们故意漏写对 [] 构造器的检查。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "header": "MessageHeader {mhIdentifiers = [\"8e8604b4-d309-4a7b-b632-334d5c54b1e8\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"8e8604b4-d309-4a7b-b632-334d5c54b1e8\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"recordTiming\",Bool False),(\"deletedCells\",Array []),(\"cellId\",String \"ed438333-389e-4677-adb9-289afcf60d2a\")]), mhMessageId = UUID {uuidToString = \"b3c8fbd7-6020-4704-9554-283373bbebf6\"}, mhSessionId = UUID {uuidToString = \"8e8604b4-d309-4a7b-b632-334d5c54b1e8\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage, mhBuffers = []}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"38cc72e6-c3f1-4eea-a938-c60e94016d64\"}, mhSessionId = UUID {uuidToString = \"8e8604b4-d309-4a7b-b632-334d5c54b1e8\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage, mhBuffers = []}",
     "output_type": "error",
     "traceback": [
      "<interactive>:1:1-37: Non-exhaustive patterns in function badExample"
     ]
    }
   ],
   "source": [
    "badExample (x:xs) = x + badExample xs\n",
    "badExample []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 如果我们将其作用于一个不能匹配的值，运行时就会报错:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 但如果某些情况，我们并不在乎某些特定的构造器，我们就可以用通配符匹配模式来定义一个默认行为:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "goodExample (x:xs) = x+goodExample xs\n",
    "goodExample _ = 0\n",
    "-- 这里还体现了模式匹配类似加了C++里面加了break的switch。有多个可匹配模式时匹配最先声明的。\n",
    "\n",
    "goodExample []\n",
    "goodExample [1,2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 记录语法\n",
    "- 给一个数据类型的每个成分写访问器函数是令人感觉重复且反味的事情:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "nicerID      (Book id _     _      ) = id\n",
    "nicerTitle   (Book _  title _      ) = title\n",
    "nicerAuthors (Book _  _     authors) = authors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 我们把这种代码叫做“样板代码（boilerplate code）”：尽管是必需的，但是又长又烦。Haskell 程序员不喜欢样板代码。幸运的是，语言的设计者提供了避免这个问题的方法：我们在定义一种数据类型的同时，就可以定义好每个成分的访问器。（逗号的位置是一个风格问题，如果你喜欢的话，也可以把它放在每行的最后。）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "data Customer = Customer Int String [String]\n",
    "                deriving (Show)\n",
    "\n",
    "customerID :: Customer -> Int\n",
    "customerID (Customer id _ _) = id\n",
    "\n",
    "customerName :: Customer -> String\n",
    "customerName (Customer _ name _) = name\n",
    "\n",
    "customerAddress :: Customer -> [String]\n",
    "customerAddress (Customer _ _ address) = address"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "header": "MessageHeader {mhIdentifiers = [\"8e8604b4-d309-4a7b-b632-334d5c54b1e8\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"8e8604b4-d309-4a7b-b632-334d5c54b1e8\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"recordTiming\",Bool False),(\"deletedCells\",Array []),(\"cellId\",String \"6d3c72f8-2232-4dda-8287-7db5679fd917\")]), mhMessageId = UUID {uuidToString = \"8a5ca3cd-7c45-4916-bd6d-8d187f3dab5c\"}, mhSessionId = UUID {uuidToString = \"8e8604b4-d309-4a7b-b632-334d5c54b1e8\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage, mhBuffers = []}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"425dad0b-d945-4804-8847-cb1e5d8ae53e\"}, mhSessionId = UUID {uuidToString = \"8e8604b4-d309-4a7b-b632-334d5c54b1e8\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage, mhBuffers = []}",
     "output_type": "error",
     "traceback": [
      "<interactive>:5:13: error:\n    • Constructor ‘Customer’ does not have field ‘customerID’\n    • In the expression: Customer {customerID = 271828, customerAddress = [\"1048576 Disk Drive\", \"Milpitas, CA 95134\", \"USA\"], customerName = \"Jane Q. Citizen\"}\n      In an equation for ‘customer2’: customer2 = Customer {customerID = 271828, customerAddress = [\"1048576 Disk Drive\", \"Milpitas, CA 95134\", ....], customerName = \"Jane Q. Citizen\"}\n<interactive>:5:13: error:\n    • Constructor ‘Customer’ does not have field ‘customerAddress’\n    • In the expression: Customer {customerID = 271828, customerAddress = [\"1048576 Disk Drive\", \"Milpitas, CA 95134\", \"USA\"], customerName = \"Jane Q. Citizen\"}\n      In an equation for ‘customer2’: customer2 = Customer {customerID = 271828, customerAddress = [\"1048576 Disk Drive\", \"Milpitas, CA 95134\", ....], customerName = \"Jane Q. Citizen\"}\n<interactive>:5:13: error:\n    • Constructor ‘Customer’ does not have field ‘customerName’\n    • In the expression: Customer {customerID = 271828, customerAddress = [\"1048576 Disk Drive\", \"Milpitas, CA 95134\", \"USA\"], customerName = \"Jane Q. Citizen\"}\n      In an equation for ‘customer2’: customer2 = Customer {customerID = 271828, customerAddress = [\"1048576 Disk Drive\", \"Milpitas, CA 95134\", ....], customerName = \"Jane Q. Citizen\"}"
     ]
    }
   ],
   "source": [
    "customer1 = Customer 271828 \"J.R. Hacker\"\n",
    "            [\"255 Syntax Ct\",\n",
    "             \"Milpitas, CA 95134\",\n",
    "             \"USA\"]\n",
    "customer2 = Customer {\n",
    "              customerID = 271828\n",
    "            , customerAddress = [\"1048576 Disk Drive\",\n",
    "                                 \"Milpitas, CA 95134\",\n",
    "                                 \"USA\"]\n",
    "            , customerName = \"Jane Q. Citizen\"\n",
    "            }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 上面👆的写法和下面👇的写法是几乎完全一致的(所以我很好奇作者为什么会说几乎完全一致？什么情况下不一致？所以可以看到没用记录语法定义，在构造的时候用记录语法会报错)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "data Customer = Customer {\n",
    "      customerID      :: CustomerID,\n",
    "      customerName    :: String,\n",
    "      customerAddress :: Address\n",
    "    } deriving (Show)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 记录语法还新增了一种更详细的标识法来新建一个值。这种标识法通常都会提升代码的可读性:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "customer1 = Customer 271828 \"J.R. Hacker\"\n",
    "            [\"255 Syntax Ct\",\n",
    "             \"Milpitas, CA 95134\",\n",
    "             \"USA\"]\n",
    "customer2 = Customer {\n",
    "              customerID = 271828\n",
    "            , customerAddress = [\"1048576 Disk Drive\",\n",
    "                                 \"Milpitas, CA 95134\",\n",
    "                                 \"USA\"]\n",
    "            , customerName = \"Jane Q. Citizen\"\n",
    "            }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 如果使用这种形式，我们还可以调换字段列表的顺序。比如在上面的例子里，name 和 address 字段的顺序就被移动过，和定义类型时的顺序不一样了。\n",
    "\n",
    "- 当我们使用记录语法来定义类型时，还会影响到该类型的打印格式:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Customer {customerID = 271828, customerName = \"J.R. Hacker\", customerAddress = [\"255 Syntax Ct\",\"Milpitas, CA 95134\",\"USA\"]}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Customer {customerID = 271828, customerName = \"Jane Q. Citizen\", customerAddress = [\"1048576 Disk Drive\",\"Milpitas, CA 95134\",\"USA\"]}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Book 173 \"Use of Weapons\" [\"Iain M. Banks\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "customer1\n",
    "customer2\n",
    "\n",
    "-- 我们没有使用记录型语法时的打印格式:\n",
    "cities = Book 173 \"Use of Weapons\" [\"Iain M. Banks\"]\n",
    "cities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  参数化类型\n",
    "- 列表的类型是多态的，即列表中的元素可以是一致的任何类型。\n",
    "- 我们也可以给自定义类型添加多态性:只要在类型定义中使用类型变量就可以做到这一点\n",
    "- 常用的Maybe类型就使用了类型变量:\n",
    "    ```\n",
    "        data Maybe a = Just a\n",
    "             | Nothing\n",
    "    ```\n",
    "- 这里的变量 a 不是普通的变量：它是一个类型变量。它意味着 `Maybe` 类型使用另一种类型作为它的参数。从而使得 Maybe 可以作用于任何类型的值:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just \"something\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Just 1.5"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "someBool = Just True\n",
    "someString = Just \"something\"\n",
    "someString\n",
    "Just 1.5\n",
    "Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Maybe 是一个多态，或者称作泛型的类型。我们向 Maybe 的类型构造器传入某种类型作为参数，例如 `Maybe Int` 或 `Maybe [Bool]`。 如我们所希望的那样，这些都是不同的类型（译注：可能省略了“但是都可以成功传入作为参数”）。\n",
    "\n",
    "- 我们可以嵌套使用参数化的类型，但要记得使用括号标识嵌套的顺序，以便 Haskell 编译器知道如何解析这样的表达式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 递归类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 列表\n",
    "- 列表这种常见的类型就是递归的：即它用自己来定义自己。为了深入了解其中的含义，让我们自己来设计一个与列表相仿的类型。我们将用 Cons 替换 (:) 构造器，用 Nil 替换 [] 构造器："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "data List a = Cons a (List a)\n",
    "            | Nil\n",
    "            deriving (Show)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- `List a`在=符号的左右两侧都有出现，我们可以说该类型的定义引用了它自己。当我们使用Cons构造器的时候，我们必须提供一个a的值作为参数一，以及一个`List a`类型的值作为参数二\n",
    "- 由于 Nil 是一个 List a 类型（译注：原文是 List 类型，可能是漏写了 a），因此我们可以将它作为 Cons 的第二个参数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nil"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Cons 0 Nil"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Cons 1 (Cons 0 Nil)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Cons 2 (Cons 1 (Cons 0 Nil))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Cons 3 (Cons 2 (Cons 1 (Cons 0 Nil)))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nil\n",
    "Cons 0 Nil\n",
    "-- 这里it是ghci上一次执行结果\n",
    "Cons 1 it\n",
    "Cons 2 it\n",
    "Cons 3 it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tip\n",
    "- 我们定义的这个List可以被当作haskel里的list吗？\n",
    "- 简单地证明一下List a类型和内置的list类型[a]拥有相同的构型。让我们设计一个函数能够接受任何一个[a]类型的值作为输入参数，并返回List a类型的一个值:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Use foldr</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">fromList (x : xs) = Cons x (fromList xs)\n",
       "fromList [] = Nil</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">fromList xs = foldr Cons Nil xs</div></div>"
      ],
      "text/plain": [
       "Line 1: Use foldr\n",
       "Found:\n",
       "fromList (x : xs) = Cons x (fromList xs)\n",
       "fromList [] = Nil\n",
       "Why not:\n",
       "fromList xs = foldr Cons Nil xs"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Cons 'd' (Cons 'u' (Cons 'r' (Cons 'i' (Cons 'a' (Cons 'n' Nil)))))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fromList (x:xs) = Cons x (fromList xs)\n",
    "fromList [] = Nil\n",
    "fromList \"durian\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 上述代码可以将每个(:)替换成Cons(这也说明(:)实际上就是一种函数的语法糖),将每个[]替换成Nil。这样就涵盖了内置list类型的全部构造器。因此我们可以说二者是同构的，它们有着相同的构型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 二叉树\n",
    "- 为了更清楚说明什么是递归类型，继续说另一个例子--定义一个二叉树类型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "data Tree a = Node a (Tree a) (Tree a) \n",
    "            | Empty\n",
    "            deriving (Show)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 而如果要在Java中实现类似的定义:\n",
    "```\n",
    "class Tree<A> {\n",
    "    A value;\n",
    "    Tree<A> left;\n",
    "    Tree<A> right;\n",
    "    \n",
    "    public Tree(A v, Tree<A> l, Tree<A> r) {\n",
    "        this.value = v;\n",
    "        this.left = l;\n",
    "        this.right = r;\n",
    "    }\n",
    "}\n",
    "``` \n",
    "- 上面是定义的不同，下面对比构造的不同:\n",
    "    - java:\n",
    "    ```\n",
    "      new Tree<String>(\n",
    "            \"parent\",\n",
    "        new Tree<String>(\"left leaf\", null, null),\n",
    "        new Tree<String>(\"right leaf\", null, null));\n",
    "    }\n",
    "    ```\n",
    "    - Haskell:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "simpleTree = Node \"parent\" \n",
    "                (Node \"left leaf\" Empty Empty)\n",
    "                (Node \"right leaf\" Empty Empty)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 练习\n",
    "1. 请给 List 类型写一个与 fromList 作用相反的函数：传入一个 List a 类型的值，返回一个 [a]:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cons 1 (Cons 2 (Cons 3 Nil))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[1,2,3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- toList Cons a as = a:(toList Cons as)  \n",
    "toList (Cons a as) = (a:toList as)\n",
    "toList Nil = []\n",
    "let myList = fromList [1,2,3]\n",
    "myList\n",
    "let list = toList myList\n",
    "list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 请仿造Java示例，定义一种只需要一个构造器的树类型。不要使用Empty构造器，而是用Maybe表示节点的子节点。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Node \"root\" (Just (Node \"left\" Nothing Nothing)) Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Node Nothing Nothing Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "MyTree Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "MyTree (Just (\"left_node\",MyTree Nothing,MyTree Nothing))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "MyTree (Just (\"right_node\",MyTree Nothing,MyTree Nothing))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "MyTree (Just (\"parent\",MyTree (Just (\"left_node\",MyTree Nothing,MyTree Nothing)),MyTree (Just (\"right_node\",MyTree Nothing,MyTree Nothing))))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- 参考原书英文版Online的讨论区，http://book.realworldhaskell.org/read/defining-types-streamlining-functions.html\n",
    "-- 比较容易想到的是这种形式，但是定义起来会非常复杂:\n",
    "data Tree1 a = Node a (Maybe (Tree1 a)) (Maybe (Tree1 a)) deriving (Show)\n",
    "let simpleTree = Node \"root\" (Just (Node \"left\" Nothing Nothing)) Nothing\n",
    "simpleTree\n",
    "let empty = Node Nothing Nothing Nothing\n",
    "empty\n",
    "\n",
    "-- 好的答案是:\n",
    "data MyTree a = MyTree (Maybe (a, MyTree a, MyTree a)) deriving (Show)\n",
    "empty = MyTree Nothing\n",
    "left_node = MyTree (Just(\"left_node\", empty, empty))\n",
    "right_node = MyTree (Just(\"right_node\", empty, empty))\n",
    "parent = MyTree (Just(\"parent\", left_node, right_node))\n",
    "empty\n",
    "left_node\n",
    "right_node\n",
    "parent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 报告错误"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 当我们的代码中出现严重错误时可以调用 Haskell 提供的标准函数 error :: String -> a。我们将希望打印出来的错误信息作为一个字符串参数传入。而该函数的类型签名看上去有些特别：它是怎么做到仅从一个字符串类型的值就生成任意类型 a 的返回值的呢？\n",
    "\n",
    "- 由于它的结果是返回类型 a，因此无论我们在哪里调用它都能得到正确类型的返回值。然而，它并不像普通函数那样返回一个值，而是立即中止求值过程，并将我们提供的错误信息打印出来。\n",
    "\n",
    "- mySecond 函数返回输入列表参数的第二个元素，假如输入列表长度不够则失败。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'i'"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "ename": "",
     "evalue": "",
     "header": "MessageHeader {mhIdentifiers = [\"af8ed28a-65a1-46cc-98e2-7daa67d7457d\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"af8ed28a-65a1-46cc-98e2-7daa67d7457d\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"recordTiming\",Bool False),(\"deletedCells\",Array []),(\"cellId\",String \"be9cd80d-a71b-4718-8a8d-8e1603931b14\")]), mhMessageId = UUID {uuidToString = \"153979cf-6d2c-42ae-91a0-072af9517839\"}, mhSessionId = UUID {uuidToString = \"af8ed28a-65a1-46cc-98e2-7daa67d7457d\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage, mhBuffers = []}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"b5486b4c-2718-45b7-8572-5ae529b5a7e1\"}, mhSessionId = UUID {uuidToString = \"af8ed28a-65a1-46cc-98e2-7daa67d7457d\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage, mhBuffers = []}",
     "output_type": "error",
     "traceback": [
      "list too short\nCallStack (from HasCallStack):\n  error, called at <interactive>:3:22 in interactive:Ghci37"
     ]
    }
   ],
   "source": [
    "mySecond::[a]->a\n",
    "mySecond xs = if null (tail xs)\n",
    "                then error \"list too short\"\n",
    "                else head (tail xs)\n",
    "\n",
    "mySecond \"xi\"\n",
    "mySecond [2]\n",
    "head (mySecond [[9]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 让过程更可控的方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 我们可以使用Maybe类型来表示有可能出现错误的情况。\n",
    "- 如果我们想指出某个操作可能会失败，可以使用 Nothing 构造器。反之则使用 Just 构造器将值包裹起来。\n",
    "\n",
    "- 让我们看看如果返回 Maybe 类型的值而不是调用 error，这样会给 mySecond 函数带来怎样的变化。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "safeSecond :: [a] -> Maybe a\n",
    "safeSecond []  = Nothing\n",
    "safeSecond xs = if null (tail xs)\n",
    "                then Nothing\n",
    "                else Just (head (tail xs))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 当传入的列表太短时，我们将 Nothing 返回给调用者。然后由他们来决定接下来做什么，假如调用 error 的话则会强制程序崩溃。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Just 2"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Just 2"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "safeSecond []\n",
    "safeSecond [1]\n",
    "safeSecond [1,2]\n",
    "safeSecond [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 复习以下前面的章节，我们还可以使用模式匹配继续增强这个函数的可读性"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tidySecond :: [a] -> Maybe a\n",
    "tidySecond (_:x:_) = Just x\n",
    "tidySecond _ = Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 引入局部变量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 在函数体内部，我们可以在任何地方使用 let 表达式引入新的局部变量。请看下面这个简单的函数，它用来检查我们是否可以向顾客出借现金。我们需要确保剩余的保证金不少于 100 元的情况下，才能出借现金，并返回减去出借金额后的余额。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "lend amount balance = let reserve    = 100\n",
    "                          newBalance = balance - amount\n",
    "                      in if balance < reserve\n",
    "                         then Nothing\n",
    "                         else Just newBalance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 这段代码中使用了 let 关键字标识一个变量声明区块的开始，用 in 关键字标识这个区块的结束。每行引入了一个局部变量。变量名在 = 的左侧，右侧则是该变量所绑定的表达式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Note\n",
    "\n",
    "特别提示\n",
    "\n",
    "请特别注意我们的用词：在 let 区块中，变量名被绑定到了一个表达式而不是一个值。由于 Haskell 是一门惰性求值的语言，变量名所对应的表达式一直到被用到时才会求值。在上面的例子里，如果没有满足保证金的要求，就不会计算 newBalance 的值。\n",
    "\n",
    "当我们在一个 let 区块中定义一个变量时，我们称之为``let`` 范围内的变量。顾名思义即是：我们将这个变量限制在这个 let 区块内。\n",
    "\n",
    "另外，上面这个例子中对空白和缩进的使用也值得特别注意。在下一节 “The offside rule and white space in an expression” 中我们会着重讲解其中的奥妙。\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 在 let 区块内定义的变量，既可以在定义区内使用，也可以在紧跟着 in 关键字的表达式中使用。\n",
    "- 一般来说，我们将代码中可以使用一个变量名的地方称作这个变量名的作用域（scope）。如果我们能使用，则说明在* 作用域*内，反之则说明在作用域外 。如果一个变量名在整个源代码的任意处都可以使用，则说明它位于最顶层的作用域。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 屏蔽"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "-- 我们可以在表达式中使用嵌套的let 区块\n",
    "foo = let a = 1\n",
    "        in let b = 2\n",
    "            in a+b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 下面的写法是完全合法的；但是在嵌套的 let 表达式里重复使用相同的变量名并不明智。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Redundant bracket</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">((let x = \"foo\" in x), x)</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">(let x = \"foo\" in x, x)</div></div>"
      ],
      "text/plain": [
       "Line 3: Redundant bracket\n",
       "Found:\n",
       "((let x = \"foo\" in x), x)\n",
       "Why not:\n",
       "(let x = \"foo\" in x, x)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "(\"foo\",1)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bar = let x = 1\n",
    "        in ((let x = \"foo\" in x), x)\n",
    "-- 如上，内部的 x 隐藏了，或称作屏蔽（shadowing）, 外部的 x。它们的变量名一样，但后者拥有完全不同的类型和值。\n",
    "bar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 我们同样也可以屏蔽一个函数的参数，并导致更加奇怪的结果。你认为下面这个函数的类型是什么？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "quux a = let a = \"foo\" \n",
    "            in a ++ \"ekk!\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 在函数的内部，由于let绑定的变量名a屏蔽了函数的参数，使得参数a没有起到任何作用，因此该参数可以是任何类型的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><span class='get-type'>quux :: forall p. p -> [Char]</span>"
      ],
      "text/plain": [
       "quux :: forall p. p -> [Char]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\"fooekk!\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    ":type quux\n",
    "quux 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Tip**\n",
    "- 我们可以给GHC设置一个有用的选项: `-fwarn-name-shadowing`。如果开启了这个功能，当屏蔽某个变量名时，GHC就会打印出一条警告。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## where 从句"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还有另一种方法也可以用来引入局部变量: where从句。where从句中的定义在其所跟随的主句中有效。下面是和lend函数类似的一个例子:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "lend2 amount balance = if amount < reserve * 0.5\n",
    "                       then Just newBalance\n",
    "                       else Nothing\n",
    "    where reserve    = 100\n",
    "          newBalance = balance - amount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 尽管刚开始使用 where 从句通常会有异样的感觉，但它对于提升可读性有着巨大的帮助。它使得读者的注意力首先能集中在表达式的一些重要的细节上，而之后再补上支持性的定义。经过一段时间以后，如果再用回那些没有 where 从句的语言，你就会怀念它的存在了。\n",
    "\n",
    "- 与 let 表达式一样，where 从句中的空白和缩进也十分重要。 在下一节 “The offside rule and white space in an expression” 中我们会着重讲解其中的奥妙。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 局部函数与全局变量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 在Haskell的语法里，定义变量和定义函数的方式非常相似。这种相似性也存在于let和where区块里: 定义局部函数就像定义局部变量一样简单"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Eta reduce</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">pluralise word counts = map plural counts</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">pluralise word = map plural</div></div>"
      ],
      "text/plain": [
       "Line 2: Eta reduce\n",
       "Found:\n",
       "pluralise word counts = map plural counts\n",
       "Why not:\n",
       "pluralise word = map plural"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pluralise::String -> [Int] -> [String]\n",
    "pluralise word counts = map plural counts\n",
    "    where plural 0 = \"no \" ++ word ++ \"s\"\n",
    "          plural 1 = \"one \" ++ word\n",
    "          plural n = show n ++ \" \" ++ word ++ \"s\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 我们定义了一个由多个等式构成的局部函数 plural。局部函数可以自由地使用其被封装在内的作用域内的任意变量：在本例中，我们使用了在外部函数 pluralise 中定义的变量 word。在 pluralise 的定义里，map 函数（我们将在下一章里再来讲解它的用法）将局部函数 plural 逐一应用于 counts 列表的每个元素。\n",
    "\n",
    "- 我们也可以在代码的一开始就定义变量，语法和定义函数是一样的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 表达式里的缩进规则和空白字符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 请看 lend 和 lend2 的定义表达式，左侧空出了一大块。这并不是随随便便写的，这些空白字符是有意义的。\n",
    "\n",
    "- Haskell 依据缩进来解析代码块。这种用排版来表达逻辑结构的方式通常被称作缩进规则。在源码文件开始的那一行，首个顶级声明或者定义可以从该行的任意一列开始，Haskell 编译器或解释器将记住这个缩进级别，并且随后出现的所有顶级声明也必须使用相同的缩进。\n",
    "\n",
    "- 以下是一个顶级缩进规则的例子。第一个文件 GoodIndent.hs 执行正常。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "-- file: ch03/GoodIndent.hs\n",
    "-- 这里是最左侧一列\n",
    "\n",
    "    -- 顶级声明可以从任一列开始\n",
    "    firstGoodIndentation = 1\n",
    "\n",
    "    -- 只要所有后续声明也这么做！\n",
    "    secondGoodIndentation = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "-- file: ch03/BadIndent.hs\n",
    "-- 这里是最左侧一列\n",
    "\n",
    "    -- 第一个声明从第 4 列开始\n",
    "    firstBadIndentation = 1\n",
    "\n",
    "-- 第二个声明从第 1 列开始，这样是非法的！\n",
    "secondBadIndentation = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 如果我们尝试在ghci里面加载这个文件将会报错：\n",
    "``` haskell\n",
    "ghci> :load GoodIndent.hs\n",
    "[1 of 1] Compiling Main             ( GoodIndent.hs, interpreted )\n",
    "Ok, modules loaded: Main.\n",
    "ghci> :load BadIndent.hs\n",
    "[1 of 1] Compiling Main             ( BadIndent.hs, interpreted )\n",
    "BadIndent.hs:8:2: parse error on input `secondBadIndentation'\n",
    "Failed, modules loaded: none.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 紧跟着的（译注：一个或多个）空白行将被视作当前行的延续，比当前行缩进更深的紧跟着的行也是如此。\n",
    "\n",
    "- let 表达式和 where 从句的规则与此类似。一旦 Haskell 编译器或解释器遇到一个 let 或 where 关键字，就会记住接下来第一个标记（token）的缩进位置。然后如果紧跟着的行是空白行或向右缩进更深，则被视作是前一行的延续。而如果其缩进和前一行相同，则被视作是同一区块内的新的一行。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 对制表符和空格说两句"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 缩进规则并不是必需"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Case表达式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 新手在使用模式时常见的问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 错误地对变量进行匹配"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Apple"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- file: ch03/BogusPattern.hs\n",
    "data Fruit = Apple | Orange\n",
    "             deriving (Show)\n",
    "\n",
    "apple = \"apple\"\n",
    "\n",
    "orange = \"orange\"\n",
    "\n",
    "whichFruit :: String -> Fruit\n",
    "\n",
    "whichFruit f = case f of\n",
    "                 \"apple\"  -> Apple\n",
    "                 \"orange\" -> Orange\n",
    "whichFruit \"apple\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 进行了错误的相等比较"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 使用守卫实现条件求值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 练习"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 写一个函数，用来计算一个列表元素的个数．出于测试要求，保证其输出的结果和标准函数 length 保持一致."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Use foldr</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">myLength [] = 0\n",
       "myLength (x : xs) = 1 + myLength xs</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">myLength xs = foldr (\\ x -> (+) 1) 0 xs</div></div><div class=\"suggestion-name\" style=\"clear:both;\">Eta reduce</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">myLen xs = h 0 xs</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">myLen = h 0</div></div>"
      ],
      "text/plain": [
       "Line 2: Use foldr\n",
       "Found:\n",
       "myLength [] = 0\n",
       "myLength (x : xs) = 1 + myLength xs\n",
       "Why not:\n",
       "myLength xs = foldr (\\ x -> (+) 1) 0 xsLine 6: Eta reduce\n",
       "Found:\n",
       "myLen xs = h 0 xs\n",
       "Why not:\n",
       "myLen = h 0"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "1000000"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "1000000"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "myLength::[a]->Int\n",
    "myLength [] = 0\n",
    "myLength (x:xs) = 1+myLength xs\n",
    "myLength [1..1000000]\n",
    "\n",
    "-- 利用守卫避免lazy\n",
    "myLen xs = h 0 xs\n",
    "    where h acc (x:xs) | acc >= 0 = h (acc + 1) xs\n",
    "          h acc [] = acc\n",
    "myLen [1..1000000]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.添加函数的类型签名于你的源文件．出于测试要求，再次加载源文件到ghci．(略)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.写一个函数，用来计算列表的平均值，即，列表元素的总和除以列表的长度．(你可能需要用到 fromIntegral 函数将列表长度变量从 integer 类型到 float 类型进行转换．)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Use foldr</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">mySum [] = 0\n",
       "mySum (x : xs) = x + mySum xs</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">mySum xs = foldr (+) 0 xs</div></div>"
      ],
      "text/plain": [
       "Line 2: Use foldr\n",
       "Found:\n",
       "mySum [] = 0\n",
       "mySum (x : xs) = x + mySum xs\n",
       "Why not:\n",
       "mySum xs = foldr (+) 0 xs"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Just 3.0"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mySum::[Float]-> Float\n",
    "mySum [] = 0\n",
    "mySum (x:xs) = x+ mySum xs\n",
    "average::[Float] -> Maybe Float\n",
    "average [] = Nothing\n",
    "average a = Just (mySum a / fromIntegral (myLength a))\n",
    "average [1,2,3,4,5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.将一个列表变成回文序列，即，他应该读起来完全一样，不管是从前往后还是从后往前．举个例子，考虑一个列表 [1,2,3]，你的函数应该返回 [1,2,3,3,2,1]．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3,2,1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "reserve4::[a]->[a]\n",
    "reserve4 [] = []\n",
    "reserve4 (x:xs) = reserve4 xs ++ [x] \n",
    "reserve4 [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5.写一个函数，用来确定他的输入是否是一个回文序列．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "judgeReserve4::(Eq a)=>[a]->Bool\n",
    "judgeReserve4 [] = True\n",
    "judgeReserve4 list = let tsil = reserve4 list \n",
    "                        in judge list tsil\n",
    "                            where \n",
    "                              judge::(Eq a)=>[a] -> [a] -> Bool\n",
    "                              judge [] [] = True\n",
    "                              judge (x:xs) (y:ys) = (x==y) && judge xs ys\n",
    "judgeReserve4 [1,2,2]\n",
    "judgeReserve4 [1,2,1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6.创造一个函数，用于排序一个包含许多列表的列表，其排序规则基于他的子列表的长度．（你可能要看看 Data.List 模块的 sortBy 函数．）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[],[1],[2,3]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import Data.List\n",
    "sortBy (\\x y -> compare (length x) (length y)) [[],[2,3],[1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7.定义一个函数，其用一个分隔符将一个包含许多列表的列表连接在一起．函数类型定义如下：\n",
    "\n",
    "``` haskell\n",
    " intersperse :: a -> [[a]] -> [a]\n",
    "```\n",
    "这个分割应该出现于列表的元素之间，除了最后一个元素末尾之外．你的函数需运行得如下所示：\n",
    "``` haskell\n",
    "ghci> :load Intersperse\n",
    "[1 of 1] Compiling Main             ( Intersperse.hs, interpreted )\n",
    "Ok, modules loaded: Main.\n",
    "ghci> intersperse ',' []\n",
    "\"\"\n",
    "ghci> intersperse ',' [\"foo\"]\n",
    "\"foo\"\n",
    "ghci> intersperse ',' [\"foo\",\"bar\",\"baz\",\"quux\"]\n",
    "\"foo,bar,baz,quux\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"ab,cd\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\"ab\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "join::a->[[a]]->[a]\n",
    "join _ [] = []\n",
    "join _ [x] = x\n",
    "join a (x:xs) = x ++ (a:join a xs)\n",
    "join ',' [\"ab\",\"cd\"]\n",
    "join ',' [\"ab\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8.使用我们在前面章节中定义的二叉树类型，写一个函数用于确定一棵二叉树的高度．高度的定义是从根节点到叶子节点经过的最大节点数．举个例子，Empty 这棵树的高度是0; Node \"x\" Empty Empty 这棵树的高度是1; Node \"x\" Empty (Node \"y\" Empty Empty) 这棵树的高度是2;依此类推．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data Tree a = Node {\n",
    "        value::a, \n",
    "        leftSon::Tree a,\n",
    "        rightSon::Tree a\n",
    "    } | Empty deriving (Show)\n",
    "treeHeight::Tree a->Int\n",
    "treeHeight Empty = 0\n",
    "treeHeight a = 1 + max (treeHeight (leftSon a)) (treeHeight (rightSon a))\n",
    "treeHeight (Node \"x\" Empty (Node \"y\" Empty Empty))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "9.考虑三个二维的点 a, b，和c．如果我们观察沿着线段ＡＢ（由a,b节点组成）和线段ＢＣ（由b,c节点组成）形成的角度，它或者转向（turn）左边，或者转向右边，或者组成一条直线．定义一个 Direction（方向）的数据类型反映这些可能的情况．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "{-@ zero :: {v:Int | v = 0} @-}\n",
    "data Point = Cartesian Double Double | Polar Double Double\n",
    "data Direction = \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "pygments_lexer": "Haskell",
   "version": "8.6.5"
  },
  "toc-autonumbering": true,
  "toc-showcode": false,
  "toc-showmarkdowntxt": false,
  "toc-showtags": false
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
